package promote.brozen.algorithm.neteasy;

/**
 * @author Brozen
 * @date 2020/9/25 3:26 PM
 * @email brozen@qq.com
 */
public class ChaZhi {

    /**
     * 有一个数组array= [9, 1, 4, 6, 3]，要找出来两个下标i，j，i < j，使array[j] - array[i] 值最大
     */
    public static void main(String[] args) {
        int[] array = new int[]{ 9, 1, 4, 6, 3 };


    }

    /**
     * 暴力解 复杂度O(n(n-1)/2)
     * @param array
     * @return
     */
    public int maxDistance1(int[] array) {
        int distance = -1;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                int m = array[j] - array[i];
                if (m > distance) {
                    distance = m;
                }
            }
        }
        return distance;
    }


    /**
     * 记录下来最小值
     * 复杂度O(n)
     */
    public int maxDistance2(int[] array) {
        int distance = 0;
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }

            if (array[i] - min > distance) {
                distance = array[i] - min;
            }
        }
        return distance;
    }


}
